There has been an increased use of handheld or dashboard-mounted travel guidance systems, for example, Global Positioning System (GPS)-embedded personal digital assistants (PDAs) and smart phones. In addition, there has been an increase in applications such as route planners, hot route finders, traffic flow analyzers, and geographical social network applications that use GPS data to achieve a better quality of service.
Typically, a GPS trajectory consists of a sequence of positions with latitude, longitude, instant speed, direction and timestamp information. However, this data can often be incorrect as a result of measurement errors caused by the limitations of typical GPS devices, as well as sampling errors caused by the sampling rate. Therefore, an observed GPS position often needs to be aligned with a road network on a digital map. This process is referred to as map-matching. The difficulty of map-matching can greatly differ depending on GPS accuracy and the sampling frequency, for example, map-matching is easier with data that is gathered frequently, and with a high degree of accuracy, than with data that is inaccurate or that is gathered less frequently.
Existing map-matching approaches generally employ an algorithm that maps sampled positions from a GPS trajectory onto vector road segments on a map. Such an approach typically considers sampled positions on a GPS trajectory while overlooking the speed and temporal data that may also be found in the GPS trajectory. These map-matching algorithms are typically most accurate when using data gathered at a high sampling rate. As sampling frequency decreases, measurement errors typically increase. However, while a high sampling rate results in increased accuracy, it also carries a greater computational cost.
Map-matching for low-sampling-rate GPS data is challenging because, as the sampling rate decreases, the interval between two neighboring positions in a trajectory increases, and less information is available to deduce the precise location of an object. A more effective approach for map-matching for low-sampling rate GPS trajectories utilizes temporal and speed data from the GPS trajectory to augment the spatial data.